package 体育课测验2;

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param numProject int整型
     * @param groups int整型ArrayList<ArrayList<>>
     * @return int整型ArrayList
     */
    static int N = 2010, n, idx;
    static int[] h = new int[N];
    static int[] e = new int[N * N];
    static int[] ne = new int[N * N];
    static int[] d = new int[N];
    static ArrayList<Integer> top = new ArrayList<>();

    public ArrayList<Integer> findOrder(int numProject, ArrayList<ArrayList<Integer>> groups) {
        // write code here
        Arrays.fill(h, -1);
        n = numProject;
        for (int i = 0; i < groups.size(); i++) {
            int a = groups.get(i).get(1), b = groups.get(i).get(0);//a->b
            add(a, b);
            d[b]++;
        }
        if (topsort()) {
            return top;
        } else {
            return new ArrayList<>();
        }
    }

    private boolean topsort() {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (d[i] == 0) {
                q.offer(i);
            }
        }
        while (!q.isEmpty()) {
            int t = q.poll();
            top.add(t);
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (--d[j] == 0) {
                    q.offer(j);
                }
            }
        }
        return top.size() == n;
    }

    private void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}
